package link_list

// https://leetcode.cn/problems/lru-cache/ leetcode-146

//type DoublyListNode struct {
//	Key  int
//	Val  int
//	Next *DoublyListNode
//	Prev *DoublyListNode
//}
//
//type LRUCache struct {
//	cache map[int]*DoublyListNode
//	head  *DoublyListNode
//	tail  *DoublyListNode
//	size  int
//}
//
//func Constructor(capacity int) LRUCache {
//	return LRUCache{
//		cache: make(map[int]*DoublyListNode, capacity),
//		size:  capacity,
//	}
//}
//
//func (this *LRUCache) Get(key int) int {
//	node, ok := this.cache[key]
//	if !ok {
//		return -1
//	}
//	this.moveToHead(node)
//	return node.Val
//}
//
//func (this *LRUCache) Put(key int, value int) {
//	if node, ok := this.cache[key]; ok {
//		node.Val = value
//		if this.tail != nil {
//			this.moveToHead(node)
//		}
//		return
//	}
//
//	node := &DoublyListNode{Key: key, Val: value}
//	defer func() { this.cache[key] = node }()
//	if this.size > 0 {
//		this.size--
//		if this.head == nil {
//			this.head = node
//			return
//		}
//
//		if this.tail == nil {
//			this.tail = this.head
//			this.head = node
//			this.head.Next = this.tail
//			this.tail.Prev = this.head
//			return
//		}
//
//		this.head.Prev = node
//		node.Next = this.head
//		this.head = node
//	} else {
//		if this.tail == nil {
//			delete(this.cache, this.head.Key)
//			this.head = node
//			return
//		}
//		this.headInsert(node)
//	}
//}
//
//func (this *LRUCache) headInsert(node *DoublyListNode) {
//	deleteKey := this.tail.Key
//	this.tail = this.tail.Prev
//	this.tail.Next = nil
//	node.Next = this.head
//	this.head.Prev = node
//	delete(this.cache, deleteKey)
//	this.head = node
//}
//
//func (this *LRUCache) moveToHead(node *DoublyListNode) {
//	nodePrev := node.Prev
//	nodeNext := node.Next
//
//	if nodePrev == nil {
//		return
//	}
//
//	nodePrev.Next = nodeNext
//	if nodeNext != nil {
//		nodeNext.Prev = nodePrev
//	} else {
//		this.tail = node.Prev
//	}
//	node.Next = this.head
//	this.head.Prev = node
//	node.Prev = nil
//	this.head = node
//}

type LRUCache struct {
	cache map[int]*DoublyListNode
	head  *DoublyListNode
	tail  *DoublyListNode
	rest  int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		cache: make(map[int]*DoublyListNode, capacity),
		rest:  capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	node, ok := this.cache[key]
	if !ok {
		return -1
	}
	this.moveToFront(node)
	return node.Val
}

func (this *LRUCache) Put(key int, value int) {
	node, ok := this.cache[key]
	if ok {
		this.moveToFront(node)
		node.Val = value
		return
	}

	node = &DoublyListNode{Key: key, Val: value}
	defer func() {
		// 必定执行的流程，可以放在defer操作，防止流程中漏写
		this.cache[key] = node
		if this.rest > 0 {
			this.rest--
		}
	}()

	// 如果是第一次插入， 则直接赋值即可
	if len(this.cache) == 0 {
		this.head = node
		this.tail = node
		return
	}

	// 如果剩余容量为0并且目前cache元素为1，则只需要删除旧数据，新节点直接替换
	if this.rest == 0 && len(this.cache) == 1 {
		delete(this.cache, this.tail.Key)
		this.head = node
		this.tail = node
		return
	}

	// 如果剩余节点为0，则需要淘汰旧数据，同时将尾节点的前驱变为尾节点，新的尾节点Next指向Nil
	if this.rest == 0 {
		deleteKey := this.tail.Key
		delete(this.cache, deleteKey)
		this.tail = this.tail.Prev
		this.tail.Next = nil
	}
	node.Next = this.head
	this.head.Prev = node
	this.head = node
}

func (this *LRUCache) moveToFront(node *DoublyListNode) {
	// 如果头结点是当前节点，不需要移动
	if this.head == node {
		return
	}

	next := node.Next
	prev := node.Prev
	prev.Next = next
	// 如果当前节点是尾节点，此时next为nil，只需要将this.tail指向prev即可，否则按照正常流程交换
	if next != nil {
		next.Prev = prev
	} else {
		this.tail = prev
	}
	this.head.Prev = node
	node.Next = this.head
	this.head = node
	// 记得最后将新的头节点的前驱指向Nil
	this.head.Prev = nil
}

type DoublyListNode struct {
	Key  int
	Val  int
	Next *DoublyListNode
	Prev *DoublyListNode
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
